import com.sun.scenario.effect.Merge;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2022-05-13
 * Time: 10:42
 */
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}
public class Solution2 {
    //合并两个链表
    public ListNode merge(ListNode list1,ListNode list2){
        ListNode res=new ListNode(-1);
        ListNode cur=res;
        while (list1!=null && list2!=null){
            if(list1.val<list2.val){
                cur.next=list1;
                list1=list1.next;
            }else{
                cur.next=list2;
                list2=list2.next;
            }
            cur=cur.next;
        }
        if(list1==null){
            cur.next=list2;
        }
        if(list2==null){
            cur.next=list1;
        }
        return res.next;
    }
    //递归划分，直到
    public ListNode divide(ArrayList<ListNode> lists,int left,int right){
        if(left>right){
            return null;  //链表数组为空的情况下   
        }
        if(left==right){ //一直都是取的左边的那个链表，保证是比较小的
            return lists.get(left);
        }
        //划分为两个区间
        int mid=(left+right)/2;
        //合并划分的两个区间，两边一直递归划分，直到只剩下一个链表，合并两边的链表
       return merge(divide(lists,left,mid),divide(lists,mid+1,right));
    }
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        //合并K个升序链表
       return divide(lists,0,lists.size()-1);
    }
}
